package com.example.lcpractice.lc;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 4. 寻找两个正序数组的中位数
 * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
 * <p>
 * 算法的时间复杂度应该为 O(log (m+n)) 。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums1 = [1,3], nums2 = [2]
 * 输出：2.00000
 * 解释：合并数组 = [1,2,3] ，中位数 2
 * 示例 2：
 * <p>
 * 输入：nums1 = [1,2], nums2 = [3,4]
 * 输出：2.50000
 * 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
 *  
 * <p>
 *  
 * <p>
 * 提示：
 * <p>
 * nums1.length == m
 * nums2.length == n
 * 0 <= m <= 1000
 * 0 <= n <= 1000
 * 1 <= m + n <= 2000
 * -106 <= nums1[i], nums2[i] <= 106
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/median-of-two-sorted-arrays
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author hd
 * @date 2022-07-08 09:51
 * @description 回文数
 */
public class Lc04 {
    public static void main(String[] args) {
        int[] ints1 = {2};
        int[] ints2 = {1};

        System.out.println(findMedianSortedArrays2(ints1, ints2));
    }

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        List<Integer> integerList = Arrays.stream(nums1).boxed().collect(Collectors.toList());
        List<Integer> integerList1 = Arrays.stream(nums2).boxed().collect(Collectors.toList());
        integerList.addAll(integerList1);
        Collections.sort(integerList);
//        System.out.println(integerList);
        int l1 = nums1.length;
        int l2 = nums2.length;
        int mid;
        mid = (l1 + l2) / 2;
        if ((l1 + l2) % 2 != 0) {
            return integerList.get(mid);
        } else {
            Integer n1 = integerList.get(mid);
            Integer n2 = integerList.get(mid - 1);
            double r = (double) n1 + n2;
            return r / 2;
        }
    }

    /**
     * 两个数组均有序小到大，只需要计算中位数的位置，
     * 用指针分别对整体小->大计数
     * 得到中位数返回
     * 两个数组长度m,n
     * 如果是奇数7，7/2=3，恰恰是为第'4'个的中位数
     * 如果是偶数8，8/2=4，4是第'5'个数，还需要前一个数字
     * 综上，需要两个指针指向当前，之前
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public static double findMedianSortedArrays2(int[] nums1, int[] nums2) {
        int len = nums1.length + nums2.length;
        boolean even = len % 2 == 0;
        int mid = len / 2;
        if (nums1.length == 0) {
            return even ? (nums2[mid] + nums2[mid - 1]) / 2.0 : nums2[mid];
        }
        if (nums2.length == 0) {
            return even ? (nums1[mid] + nums1[mid - 1]) / 2.0 : nums1[mid];
        }
        int cur = 0;
        int pre = 0;
        int left = 0;
        int right = 0;
        while (mid >= 0) {
            pre = cur;
            //两指针没越界，左指向更小
            if (left < nums1.length && right < nums2.length && nums1[left] <= nums2[right]) {
                cur = nums1[left];
                left++;
                //两指针没越界，右指向更小
            } else if (left < nums1.length && right < nums2.length && nums1[left] > nums2[right]) {
                cur = nums2[right];
                right++;
                //左越界，右边自己递进
            } else if (left >= nums1.length) {
                cur = nums2[right];
                right++;
                //右越界，左边自己递进
            } else {
                cur = nums1[left];
                left++;
            }
            //计数位置已经到达，根据奇数偶数返回
            if (mid == 0) {
                return even ? (cur + pre) / 2.0 : cur;
            }
            mid--;

        }
        return 0;
    }
}

